//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 注意：给定 n 是一个正整数。 
//
// 示例 1： 
//
// 输入： 2
//输出： 2
//解释： 有两种方法可以爬到楼顶。
//1.  1 阶 + 1 阶
//2.  2 阶 
//
// 示例 2： 
//
// 输入： 3
//输出： 3
//解释： 有三种方法可以爬到楼顶。
//1.  1 阶 + 1 阶 + 1 阶
//2.  1 阶 + 2 阶
//3.  2 阶 + 1 阶
// 
// Related Topics 记忆化搜索 数学 动态规划 
// 👍 2046 👎 0

package com.cute.leetcode.editor.cn;
public class ClimbingStairs {
    public static void main(String[] args) {
        Solution solution = new ClimbingStairs().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 注意，只用dfs会超时的，回溯次数太多了
         * 需要用到记忆化递归？
         * 斐波那契数列？？
         * 能走到n的时候可以从n-1爬上来，也能从n-2处爬上来，所有f(n) = f(n-1) + f(n-2)
         * 程序中将空间压缩了，没有构建数列，只用了两个变量来存储值
         * 从 n = 3 开始的，避免了n==0的这种情况
         */
        public int climbStairs(int n) {
            if (n<=2) return n;
            int pre = 1;
            int cur = 2;
            int temp;
            for (int i = 3; i <= n ; ++i) {
                temp = pre;
                pre = cur;
                cur = cur + temp;
            }
            return cur;
        }
        /**
         * 增加难度，每次可以爬1-m个台阶，问到第n处有多少种方法
         */
        public int climbStairs(int n, int m) {
            int[] dp = new int[n+1];
            //这里初始为1的原因是：因为可以一次走m个台阶，那么当i-j = 0的时候也是可以一步上来的
            //所以dp[0]必须为1，如果为0的话会少一次
            // 或者把dp[i<=m]的位置先都初始化为1，此时就可以把dp[0]初始为0了
            dp[0]=1;
            for (int i = 1; i <= n ; i++) {
                for (int j = 1; j <= m ; j++) {
                    if (i-j >= 0) dp[i] += dp[i-j];
                }
            }
            return dp[n];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}